{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Area Rectangle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #hash-table #math #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #哈希表 #数学 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minAreaRect"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小面积矩形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定在 xy 平面上的一组点，确定由这些点组成的矩形的最小面积，其中矩形的边平行于 x 轴和 y 轴。</p>\n",
    "\n",
    "<p>如果没有任何矩形，就返回 0。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[[1,1],[1,3],[3,1],[3,3],[2,2]]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>1 &lt;= points.length &lt;= 500</code></li>\n",
    "\t<li><code>0 &lt;=&nbsp;points[i][0] &lt;=&nbsp;40000</code></li>\n",
    "\t<li><code>0 &lt;=&nbsp;points[i][1] &lt;=&nbsp;40000</code></li>\n",
    "\t<li>所有的点都是不同的。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-area-rectangle](https://leetcode.cn/problems/minimum-area-rectangle/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-area-rectangle](https://leetcode.cn/problems/minimum-area-rectangle/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1],[1,3],[3,1],[3,3],[2,2]]', '[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points):\n",
    "        n = len(points)\n",
    "        nx = len(set(x for x, y in points))\n",
    "        ny = len(set(y for x, y in points))\n",
    "        if nx == n or ny == n:\n",
    "            return 0\n",
    "\n",
    "        p = collections.defaultdict(list)\n",
    "        if nx > ny:\n",
    "            for x, y in points:\n",
    "                p[x].append(y)\n",
    "        else:\n",
    "            for x, y in points:\n",
    "                p[y].append(x)\n",
    "\n",
    "        lastx = {}\n",
    "        res = float('inf')\n",
    "        for x in sorted(p):\n",
    "            p[x].sort()\n",
    "            for i in range(len(p[x])):\n",
    "                for j in range(i):\n",
    "                    y1, y2 = p[x][j], p[x][i]\n",
    "                    if (y1, y2) in lastx:\n",
    "                        res = min(res, (x - lastx[y1, y2]) * abs(y2 - y1))\n",
    "                    lastx[y1, y2] = x\n",
    "        return res if res < float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        area = 0\n",
    "        for n,i in enumerate(points):\n",
    "            for j in points[n+1:]:\n",
    "                if i[0] == j[0] or i[1] == j[1]:\n",
    "                    continue\n",
    "                if area > 0 and abs((i[0] - j[0]) * (i[1] - j[1])) >= area:\n",
    "                    continue\n",
    "                if [i[0],j[1]] in points and [j[0],i[1]] in points:\n",
    "                    if area == 0:\n",
    "                        area = abs((i[0] - j[0]) * (i[1] - j[1]))\n",
    "                    else:\n",
    "                        area = min([area,abs((i[0] - j[0]) * (i[1] - j[1]))])\n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points):\n",
    "        area = 0\n",
    "        mem = set()\n",
    "        for x1,y1 in points:\n",
    "            for x2,y2 in mem:\n",
    "                if (x2,y1) in mem and (x1,y2) in mem:\n",
    "                    if not area:\n",
    "                        area = abs(x2-x1)*abs(y2-y1)\n",
    "                    else:\n",
    "                        if abs(x2-x1)*abs(y2-y1) < area:\n",
    "                            area = abs(x2-x1)*abs(y2-y1)\n",
    "            mem.add((x1,y1))\n",
    "        return area\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        pset = dict()\n",
    "        for v in points:\n",
    "            pset[(v[0], v[1])] = True\n",
    "        ans = 2**31 - 1\n",
    "        for i, v1 in enumerate(points):\n",
    "            for v2 in points[i+1:]:\n",
    "                if v1[0] != v2[0] and v1[1] != v2[1] and (v1[0], v2[1]) in pset and (v2[0], v1[1]) in pset:\n",
    "                    ans = min(ans, abs((v1[0] - v2[0]) * (v1[1] - v2[1])))\n",
    "        if ans == 2**31 - 1: return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "\n",
    "        rec_set = set() #为了加速查找，以空间换取时间\n",
    "        for [x,y] in points:\n",
    "            rec_set.add((x,y))\n",
    "        \n",
    "        ######## 用对角线，往前探的思想，是因为可以计算。比暴力遍历要好很多。 有计算的（有目的地搜） 好于 暴力搜（漫无目的地搜）\n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            [x1, y1] = points[i]\n",
    "            for j in range(i + 1, n):\n",
    "                [x2, y2] = points[j]\n",
    "                if x1 != x2 and y1 != y2:   #不在同行或者同列，可以构成对角线\n",
    "                    p3 = (x1, y2)\n",
    "                    p4 = (x2, y1)\n",
    "                    if p3 in rec_set and p4 in rec_set:     #往前探的思想\n",
    "                        cur = abs(x1 - x2) * abs(y1 - y2)   #当前的面积\n",
    "                        res = min(res, cur)\n",
    "        return 0 if res == float('inf') else res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        s=set()\n",
    "        for point in points:\n",
    "            s.add((point[0],point[1]))\n",
    "        res=float('inf')\n",
    "        for  i in range(len(points)):\n",
    "            x1,y1=points[i]\n",
    "            for j in range(i+1,len(points)):\n",
    "                x2,y2=points[j]\n",
    "                if x1!=x2 and y1!=y2:\n",
    "                    if (x1,y2) in s and (x2,y1) in s:\n",
    "                        t=abs(x1-x2)*abs(y1-y2)\n",
    "                        res=min(res,t)\n",
    "        return res if res!=float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minAreaRect(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(points)\n",
    "        if n <= 3:\n",
    "            return 0\n",
    "        area = 1600000001\n",
    "\n",
    "        #以空间换时间\n",
    "        rec_set = set()\n",
    "        for p in points:\n",
    "            #将二维变成一维\n",
    "            rec_set.add(40001 * p[0] + p[1])\n",
    "        for i in range(n):\n",
    "            for j in range(1,i):\n",
    "                x1 = points[i][0]\n",
    "                y1 = points[i][1]\n",
    "                x2 = points[j][0]\n",
    "                y2 = points[j][1]\n",
    "                if x1 != x2 and y1 != y2:\n",
    "                    if (40001 * x1 + y2) in rec_set and (40001 * x2 + y1) in rec_set:\n",
    "                    # if [x1,y2] in points and [x2,y1] in points:\n",
    "                        area = min(abs(x2 - x1) * abs(y2 - y1),area)\n",
    "        if area == 1600000001:\n",
    "            return 0\n",
    "        else:\n",
    "            return area\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        points_set = set(map(tuple, points)) # simplify rectangle forming\n",
    "        res = float('inf')\n",
    "        \n",
    "        # enumerate 2 pts from list, check if they can form rectangle\n",
    "        l = len(points)\n",
    "        for i in range(l):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i + 1, l):\n",
    "                x2, y2 = points[j]\n",
    "\n",
    "                # use pt1, pt2, try form rectangular with these 2 pts sitting on diagnal\n",
    "                if x1 != x2 and y1 != y2 and (x1, y2) in points_set and (x2, y1) in points_set:\n",
    "                    res = min(res, abs(x1 - x2) * abs(y1 - y2))\n",
    "\n",
    "        return res if res != float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        s = set()\n",
    "        for x, y in points:\n",
    "            s.add((x, y))\n",
    "        res = float('inf')\n",
    "        for i in range(len(points) - 1):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i + 1, len(points)):\n",
    "                x2, y2 = points[j]\n",
    "                if x1 != x2 and y1 != y2:\n",
    "                    p1 = (x1, y2)\n",
    "                    p2 = (x2, y1)\n",
    "                    if p1 in s and p2 in s:\n",
    "                        res = min(res, abs(x1 - x2) * abs(y1 - y2))\n",
    "        return 0 if res == float('inf') else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "\n",
    "        rec_set = set() #为了加速查找，以空间换取时间\n",
    "        for [x,y] in points:\n",
    "            rec_set.add((x,y))\n",
    "        \n",
    "        ######## 用对角线，往前探的思想，是因为可以计算。比暴力遍历要好很多。 有计算的（有目的地搜） 好于 暴力搜（漫无目的地搜）\n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            [x1, y1] = points[i]\n",
    "            for j in range(i + 1, n):\n",
    "                [x2, y2] = points[j]\n",
    "                if x1 != x2 and y1 != y2:   #不在同行或者同列，可以构成对角线\n",
    "                    p3 = (x1, y2)\n",
    "                    p4 = (x2, y1)\n",
    "                    if p3 in rec_set and p4 in rec_set:     #往前探的思想\n",
    "                        cur = abs(x1 - x2) * abs(y1 - y2)   #当前的面积\n",
    "                        res = min(res, cur)\n",
    "        return 0 if res == float('inf') else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        s = set(map(tuple, points))\n",
    "        res = float('inf')\n",
    "\n",
    "        for j, p2 in enumerate(points):\n",
    "            for i in range(j):\n",
    "                p1 = points[i]\n",
    "                if (p1[0] != p2[0]) and (p1[1] != p2[1]) and ((p1[0], p2[1]) in s) and ((p2[0], p1[1]) in s):\n",
    "                    res = min(res, abs((p1[0]-p2[0])*(p1[1]-p2[1])))\n",
    "        \n",
    "        return res if res < float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minAreaRect(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(points)\n",
    "        area = 1600000000\n",
    "        rec_set = set()\n",
    "        for [x,y] in points:\n",
    "            rec_set.add((x,y))\n",
    "        for i in range(n):\n",
    "            for j in range(1,i):\n",
    "                x1 = points[i][0]\n",
    "                y1 = points[i][1]\n",
    "                x2 = points[j][0]\n",
    "                y2 = points[j][1]\n",
    "                if x1 != x2 and y1 != y2:\n",
    "                    if (x1,y2) in rec_set and (x2,y1) in rec_set:\n",
    "                        area = min(abs(x2 - x1) * abs(y2 - y1),area)\n",
    "        if area == 1600000000:\n",
    "            return 0\n",
    "        else:\n",
    "            return area\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "\n",
    "        rec_set = set() #为了加速查找，以空间换取时间\n",
    "        for [x,y] in points:\n",
    "            rec_set.add((x,y))\n",
    "        \n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            [x1, y1] = points[i]\n",
    "            for j in range(i + 1, n):\n",
    "                [x2, y2] = points[j]\n",
    "                if x1 != x2 and y1 != y2:   #不在同行或者同列，可以构成对角线\n",
    "                    p3 = (x1, y2)\n",
    "                    p4 = (x2, y1)\n",
    "                    if p3 in rec_set and p4 in rec_set:     #往前探的思想\n",
    "                        cur = abs(x1 - x2) * abs(y1 - y2)   #当前的面积\n",
    "                        res = min(res, cur)\n",
    "        return 0 if res == float('inf') else res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        res = inf\n",
    "        # 1,1 1,2  1,3   2,3 2,4 2,5 3,3  3,6, 3,9\n",
    "        s = set()\n",
    "        def hash(x, y):\n",
    "            return x * (10 ** 5) + y\n",
    "        for _, [x, y] in enumerate(points):\n",
    "            s.add(hash(x, y))\n",
    "        n = len(points)\n",
    "        for i, [x1, y1] in enumerate(points):\n",
    "            for j in range(i + 1, n):\n",
    "                x2, y2 = points[j]\n",
    "                if x1 == x2 or y1 == y2:\n",
    "                    continue\n",
    "                x3, y3 = x1, y2\n",
    "                x4, y4 = x2, y1\n",
    "                h3, h4 = hash(x3, y3), hash(x4, y4)\n",
    "                if h3 not in s or h4 not in s:\n",
    "                    continue\n",
    "                res = min(res, abs(y3 - y4) * abs(x3 - x4))\n",
    "        return res if res != inf else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        res = inf\n",
    "        n = len(points)\n",
    "        s = set( (  (x[0], x[1]) for x in points  ) )\n",
    "\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                p1 = points[i]\n",
    "                p2 = points[j]\n",
    "\n",
    "                if p1[0] == p2[0]: continue\n",
    "                if p1[1] == p2[1]: continue\n",
    "\n",
    "                if (p1[0],p2[1]) in s and (p2[0],p1[1]) in s:\n",
    "                    tmp = abs(p1[0]-p2[0]) * abs(p1[1]-p2[1])\n",
    "                    res = min(res, tmp)\n",
    "\n",
    "        return res if res != inf else 0\n",
    "                    \n",
    "                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        points_hash = set([tuple(e) for e in points])\n",
    "        ans = float('inf')\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i):\n",
    "                if points[i][0] != points[j][0] and points[i][1] != points[j][1] and (points[i][0], points[j][1]) in points_hash and (points[j][0], points[i][1]) in points_hash:\n",
    "                    ans = min(ans, abs(points[i][1] - points[j][1]) * abs(points[i][0] - points[j][0]))\n",
    "        if ans == float('inf'):\n",
    "            return 0\n",
    "        else:\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        points_set = set(tuple(p) for p in points)\n",
    "        res = inf\n",
    "        n = len(points)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                x1, y1 = points[i]\n",
    "                x2, y2 = points[j]\n",
    "                if x1 == x2 or y1 == y2:\n",
    "                    continue\n",
    "                if (x1, y2) in points_set and (x2, y1) in points_set:\n",
    "                    res = min(res, abs(x1-x2)*abs(y1-y2))\n",
    "        if res == inf:\n",
    "            return 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        pts = set(map(tuple, points))\n",
    "        res = float('inf')\n",
    "        lens = len(points)\n",
    "        for idx in range(lens - 1):\n",
    "            for jdx in range(idx + 1, lens):\n",
    "                if points[idx][0] != points[jdx][0] and points[idx][1] != points[jdx][1] \\\n",
    "                    and (points[idx][0], points[jdx][1]) in pts \\\n",
    "                    and (points[jdx][0], points[idx][1]) in pts:\n",
    "                    res = min(res, abs(points[idx][0]-points[jdx][0]) * abs(points[idx][1]-points[jdx][1]))\n",
    "        if res == float('inf'):\n",
    "            return 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        x_ylist = {}\n",
    "        for x, y in points:\n",
    "            if x in x_ylist.keys():\n",
    "                x_ylist[x].append(y)\n",
    "            else:\n",
    "                x_ylist[x] = [y]\n",
    "        x_list = list(x_ylist.keys())\n",
    "        x_list.sort()\n",
    "        minarea = 2**31\n",
    "        find = False\n",
    "        for i in range(len(x_list)-1):\n",
    "            x_i = x_list[i]\n",
    "            if len(x_ylist[x_i])<2:\n",
    "                continue\n",
    "            for j in range(i+1, len(x_list)):\n",
    "                x_j = x_list[j]\n",
    "                if len(x_ylist[x_j])<2:\n",
    "                    continue\n",
    "                a = set(x_ylist[x_i])\n",
    "                b = set(x_ylist[x_j])\n",
    "                c = list(a.intersection(b))\n",
    "                if len(c) < 2:\n",
    "                    continue\n",
    "                c.sort()\n",
    "                for k in range(len(c)-1):\n",
    "                    find = True\n",
    "                    minarea = min(minarea, (x_j-x_i) * (c[k+1]-c[k]))\n",
    "        return minarea if find else 0\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        res = 1e9\n",
    "        points.sort()\n",
    "        pointset = set(map(tuple, points))\n",
    "        for i, (x0, y0) in enumerate(points):\n",
    "            for x1, y1 in points[i+1:]:\n",
    "                if x1 <= x0 or y1 <= y0:\n",
    "                    continue\n",
    "                if (x0, y1) in pointset and (x1, y0) in pointset:\n",
    "                    square = (x1-x0) * (y1-y0)\n",
    "                    if square:\n",
    "                        res = min(res, square)\n",
    "        \n",
    "        return res if res < 1e9 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        pointsSet = set(map(tuple, points))\n",
    "        points.sort()\n",
    "        ans = inf\n",
    "        # 枚举对角线\n",
    "        for i, (x0, y0) in enumerate(points):\n",
    "            for x1, y1 in points[i + 1:]:\n",
    "                # 对角线斜率为0无法构成矩形\n",
    "                if x0 == x1 or y0 == y1: continue\n",
    "                # 若另一条对角线的两个点也存在于points中则计算此矩形面积\n",
    "                if (x0, y1) in pointsSet and (x1, y0) in pointsSet and (val := abs(x0 - x1) * abs(y0 - y1)) < ans: ans = val\n",
    "        return ans if ans < inf else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "      # 最后判断由这条对角线确定的矩形的另外两个点是否在哈希表中，如果存在就是一个合法的矩形并更新最小面积。\n",
    "        n = len(points)\n",
    "        rec_set = set([(x, y) for x, y in points])\n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            (x1, y1) = points[i]\n",
    "            for j in range(i+1, n):\n",
    "                (x2, y2) = points[j]\n",
    "                if x1 != x2 and y1 != y2:\n",
    "                    p3 = (x1, y2) # 对角线\n",
    "                    p4 = (x2, y1)\n",
    "                    if p3 in rec_set and p4 in rec_set:\n",
    "                        cur = abs(x1 - x2) * abs(y1 - y2)\n",
    "                        res = min(res, cur)\n",
    "        return 0 if res == float('inf') else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        point_set = set([(x, y) for x, y in points])\n",
    "        res = float('inf')\n",
    "        for i in range(len(points)):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i):\n",
    "                x2, y2 = points[j]\n",
    "                if x1 == x2 or y1 == y2:\n",
    "                    # 不可能为对角线, 应当是行或者列\n",
    "                    continue\n",
    "                \n",
    "                if (x1, y2) in point_set and (x2, y1) in point_set:\n",
    "                    area = abs(x1 - x2) * abs(y1 - y2)\n",
    "                    res = min(res, area)\n",
    "        return res if res < float('inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "\n",
    "        res_rec = set()\n",
    "        for [x,y] in points:\n",
    "            res_rec.add((x,y))\n",
    "        \n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            [x1,y1] = points[i]\n",
    "            for j in range(i+1,n):\n",
    "                [x2,y2] = points[j]\n",
    "                if x1 != x2 and y1 != y2:\n",
    "                    p1 = (x1,y2)\n",
    "                    p2 = (x2,y1)\n",
    "                    if p1 in res_rec and p2 in res_rec:\n",
    "                        cur_area = abs(x1-x2) * abs(y1-y2)\n",
    "                        res = min(res,cur_area)\n",
    "        return res if res!=float('inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        s = set()\n",
    "        for x, y in points:\n",
    "            s.add((x, y))\n",
    "        res = float('inf')\n",
    "        for i in range(len(points) - 1):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i + 1, len(points)):\n",
    "                x2, y2 = points[j]\n",
    "                if x1 != x2 and y1 != y2:\n",
    "                    p1 = (x1, y2)\n",
    "                    p2 = (x2, y1)\n",
    "                    if p1 in s and p2 in s:\n",
    "                        res = min(res, abs(x1 - x2) * abs(y1 - y2))\n",
    "        return 0 if res == float('inf') else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        pset = dict()\n",
    "        for v in points:\n",
    "            pset[(v[0], v[1])] = True\n",
    "        ans = inf\n",
    "        for i, v1 in enumerate(points):\n",
    "            for v2 in points[i+1:]:\n",
    "                if v1[0] != v2[0] and v1[1] != v2[1] and (v1[0], v2[1]) in pset and (v2[0], v1[1]) in pset:\n",
    "                    ans = min(ans, abs((v1[0] - v2[0]) * (v1[1] - v2[1])))\n",
    "        return ans if ans < inf else 0 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        # 将points全部存入一个set容器中\n",
    "        p_set = set(map(tuple, points))\n",
    "        # 枚举对角线\n",
    "        ans = float(\"inf\")\n",
    "        for i, p1 in enumerate(points):\n",
    "            for j in range(i+1, len(points)):\n",
    "                p2 = points[j]\n",
    "                if p1[0] != p2[0] and p1[1] != p2[1] and \\\n",
    "                (p1[0], p2[1]) in p_set and (p2[0], p1[1]) in p_set:\n",
    "                    ans = min(ans, abs((p1[1] - p2[1]) * (p1[0] - p2[0])))\n",
    "        return 0 if ans == float(\"inf\") else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minAreaRect(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(points)\n",
    "        if n <= 3:\n",
    "            return 0\n",
    "\n",
    "        area = 1600000001\n",
    "\n",
    "        #以空间换时间\n",
    "        rec_set = set()\n",
    "        for x1,y1 in points:\n",
    "            for x2,y2 in rec_set:\n",
    "                if (x2,y1) in rec_set and (x1,y2) in rec_set:\n",
    "                    area = min(abs(x2 - x1) * abs(y2 - y1),area)\n",
    "            rec_set.add((x1,y1))\n",
    "        if area == 1600000001:\n",
    "            return 0\n",
    "        else:\n",
    "            return area\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "#         s=[]\n",
    "#         for i in range(len(points)):\n",
    "#             for j in range(i+1,len(points)):\n",
    "#                 if [points[i][0],points[j][1]] in points and [points[j][0],points[i][1]] in points and points[i][0]!=points[j][0] and points[i][1]!=points[j][1]:\n",
    "#                     s.append(abs((points[i][0]-points[j][0])*(points[i][1]-points[j][1])))\n",
    "#         return min(s) if s else 0\n",
    "class Solution(object):\n",
    "    def minAreaRect(self, points):\n",
    "        S = set(map(tuple, points))\n",
    "        ans = float('inf')\n",
    "        for j, p2 in enumerate(points):\n",
    "            for i in range(j):\n",
    "                p1 = points[i]\n",
    "                if (p1[0] != p2[0] and p1[1] != p2[1] and\n",
    "                        (p1[0], p2[1]) in S and (p2[0], p1[1]) in S):\n",
    "                    ans = min(ans, abs(p2[0] - p1[0]) * abs(p2[1] - p1[1]))\n",
    "        return ans if ans < float('inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        \n",
    "\n",
    "\n",
    "        s = set()\n",
    "        for x, y in points:\n",
    "            s.add((x, y))\n",
    "        res = float('inf')\n",
    "        for i in range(len(points) - 1):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i + 1, len(points)):\n",
    "                x2, y2 = points[j]\n",
    "                if x1 != x2 and y1 != y2:\n",
    "                    p1 = (x1, y2)\n",
    "                    p2 = (x2, y1)\n",
    "                    if p1 in s and p2 in s:\n",
    "                        res = min(res, abs(x1 - x2) * abs(y1 - y2))\n",
    "        return 0 if res == float('inf') else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "\n",
    "        rec_set = set() #为了加速查找，以空间换取时间\n",
    "        for [x,y] in points:\n",
    "            rec_set.add((x,y))\n",
    "        \n",
    "        ######## 用对角线，往前探的思想，是因为可以计算。比暴力遍历要好很多。 有计算的（有目的地搜） 好于 暴力搜（漫无目的地搜）\n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            [x1, y1] = points[i]\n",
    "            for j in range(i + 1, n):\n",
    "                [x2, y2] = points[j]\n",
    "                if x1 != x2 and y1 != y2:   #不在同行或者同列，可以构成对角线\n",
    "                    p3 = (x1, y2)\n",
    "                    p4 = (x2, y1)\n",
    "                    if p3 in rec_set and p4 in rec_set:     #往前探的思想\n",
    "                        cur = abs(x1 - x2) * abs(y1 - y2)   #当前的面积\n",
    "                        res = min(res, cur)\n",
    "        return 0 if res == float('inf') else res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        st = set(map(tuple, points))\n",
    "        ans = float('inf')\n",
    "        for i in range(len(points)):\n",
    "            x0, y0 = points[i]\n",
    "            for j in range(i+1, len(points)):\n",
    "                x1, y1 = points[j]\n",
    "                if x0 == x1 or y0 == y1:\n",
    "                    continue\n",
    "                if (x0, y1) not in st or (x1, y0) not in st:\n",
    "                    continue\n",
    "                now = abs(x0 - x1) * abs(y0 - y1)\n",
    "                ans = min(ans, now)\n",
    "        if ans == float('inf'):\n",
    "            return 0\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "\n",
    "        res_rec = set()\n",
    "        for [x,y] in points:\n",
    "            res_rec.add((x,y))\n",
    "        \n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            [x1,y1] = points[i]\n",
    "            for j in range(i+1,n):\n",
    "                [x2,y2] = points[j]\n",
    "                if x1 != x2 and y1 != y2: # 能构成对角线\n",
    "                    p1 = (x1,y2)\n",
    "                    p2 = (x2,y1)\n",
    "                    if p1 in res_rec and p2 in res_rec: # 另外两个点也是存在的\n",
    "                        cur_area = abs(x1-x2) * abs(y1-y2)\n",
    "                        res = min(res,cur_area)\n",
    "        return res if res!=float('inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        dx,dy = defaultdict(list),defaultdict(list)\n",
    "        points.sort(key = lambda x:x[1])\n",
    "        for x,y in points:\n",
    "            dx[x].append(y)\n",
    "        points.sort()\n",
    "        for x,y in points:\n",
    "            dy[y].append(x)\n",
    "        ans = inf\n",
    "        for x,y_list in dx.items():\n",
    "            if len(y_list) < 2:\n",
    "                continue\n",
    "            for i in range(len(y_list)):\n",
    "                for j in range(i + 1,len(y_list)):\n",
    "                    for x1,y_list1 in dx.items():\n",
    "                        if x1 > x and y_list[i] in y_list1 and y_list[j] in y_list1:\n",
    "                            ans = min(ans,(x1 - x)*(y_list[j] - y_list[i]))\n",
    "        return ans if ans < inf else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        rowmap = {}\n",
    "        rowlist = set()\n",
    "        for x, y in points:\n",
    "            if(x not in rowmap):\n",
    "                rowmap[x] = set()\n",
    "            rowmap[x].add(y)\n",
    "            rowlist.add(x)\n",
    "        rowlist = list(rowlist)\n",
    "        result = float('inf')\n",
    "        for i in range(len(rowlist)):\n",
    "            x1 = rowlist[i]\n",
    "            for j in range(i+1,len(rowlist)):\n",
    "                x2 = rowlist[j]\n",
    "                yset = rowmap[x1] & rowmap[x2]\n",
    "                if(len(yset) < 2):\n",
    "                    continue\n",
    "                yset = sorted(yset)\n",
    "                for i in range(1,len(yset)):\n",
    "                    result = min(result, (yset[i]-yset[i-1])*abs(x1-x2))\n",
    "        return result if result < float('inf') else 0\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        maps = collections.defaultdict(bool)\n",
    "        ans = inf\n",
    "        n = len(points)\n",
    "        for x, y in points:\n",
    "            maps[(x, y)] = True\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                a, b = points[i], points[j]\n",
    "                if maps[(a[0], b[1])] and maps[(b[0], a[1])]:\n",
    "                    area = abs(a[0] - b[0]) * abs(a[1] - b[1])\n",
    "                    if area > 0 and area < ans:\n",
    "                        ans = area\n",
    "        return 0 if ans == inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        point_set = set(map(tuple, points))\n",
    "        min_area = float('inf')\n",
    "\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i + 1, len(points)):\n",
    "                p1, p2 = points[i], points[j]\n",
    "                if p1[0] != p2[0] and p1[1] != p2[1]:\n",
    "                    if (p1[0], p2[1]) in point_set and (p2[0], p1[1]) in point_set:\n",
    "                        area = abs(p2[0] - p1[0]) * abs(p2[1] - p1[1])\n",
    "                        min_area = min(min_area, area)\n",
    "        return min_area if min_area != float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "      q=set()\n",
    "      for x in points:\n",
    "         q.add((x[0],x[1]))\n",
    "      n=len(points)\n",
    "      ans=inf\n",
    "      for i in range(n-1):\n",
    "        x=points[i][0]\n",
    "        y=points[i][1]    \n",
    "        for j in range(i+1,n):\n",
    "           a=points[j][0]\n",
    "           b=points[j][1]\n",
    "           if a==x or b==y:\n",
    "               continue\n",
    "           if (x,b) in q and (a,y) in q:\n",
    "               ans=min(ans,abs(x-a)*abs(y-b))\n",
    "      return ans if ans!=inf else 0              "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        set_all = set(map(tuple, points))\n",
    "        res = inf\n",
    "        flg = 0\n",
    "\n",
    "        for p1 in points:\n",
    "            for p2 in points:\n",
    "                if p2[0] == p1[0]:\n",
    "                    continue\n",
    "                if p2[1] == p1[1]:\n",
    "                    continue\n",
    "\n",
    "                if (p1[0], p2[1]) in set_all and (p2[0], p1[1]) in set_all:\n",
    "                    res = min(res, abs( (p1[0]-p2[0]) * (p1[1]-p2[1]) ))\n",
    "                    flg = 1\n",
    "        return res if flg else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        grid = {}\n",
    "        for i in range(n):\n",
    "            x, y = points[i]\n",
    "            grid[x * 40001 + y] = 1\n",
    "\n",
    "        \n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                p1, p2 = points[i], points[j]\n",
    "                x1, y1 = p1\n",
    "                x2, y2 = p2\n",
    "                if(x1 != x2 and y1 != y2):\n",
    "                    if x1*40001 + y2 in grid and x2*40001 + y1 in grid:\n",
    "                        res = min(res, abs(x1-x2) * abs(y1- y2))\n",
    "\n",
    "        return res if res != float('inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        x_ylist = {}\n",
    "        for x, y in points:\n",
    "            if x in x_ylist.keys():\n",
    "                x_ylist[x].append(y)\n",
    "            else:\n",
    "                x_ylist[x] = [y]\n",
    "        x_list = list(x_ylist.keys())\n",
    "        x_list.sort()\n",
    "        # print(x_list)\n",
    "        # print(x_ylist)\n",
    "        minarea = 2**31\n",
    "        find = False\n",
    "        for i in range(len(x_list)-1):\n",
    "            if len(x_ylist[x_list[i]])<2:\n",
    "                continue\n",
    "            for j in range(i+1, len(x_list)):\n",
    "                if len(x_ylist[x_list[j]])<2:\n",
    "                    continue\n",
    "                a = set(x_ylist[x_list[i]])\n",
    "                b = set(x_ylist[x_list[j]])\n",
    "                c = list(a.intersection(b))\n",
    "                if len(c) < 2:\n",
    "                    continue\n",
    "                c.sort()\n",
    "                for k in range(len(c)-1):\n",
    "                    find = True\n",
    "                    # print(i, j, k, c[k+1], c[k])\n",
    "                    minarea = min(minarea, (x_list[j]-x_list[i]) * (c[k+1]-c[k]))\n",
    "        return minarea if find else 0\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        lg = len(points)\n",
    "        pset = set((x,y) for x,y in points)\n",
    "        res = math.inf\n",
    "        for i, [x1,y1] in enumerate(points):\n",
    "            for j, [x2,y2] in enumerate(points[i+1:]):\n",
    "                if (x1-x2)*(y1-y2)!=0 and (x1,y2) in pset and (x2,y1) in pset:\n",
    "                    res = min(res, abs((x1-x2)*(y1-y2)))\n",
    "        return 0 if res == math.inf else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        nodes = {tuple(node) for node in points}\n",
    "        m = len(points)\n",
    "        ans = 1600000001\n",
    "        for i in range(m):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i + 1, m):\n",
    "                x2, y2 = points[j]\n",
    "                if x1 == x2 or y1 == y2:\n",
    "                    continue\n",
    "                if (x1, y2) in nodes and (x2, y1) in nodes:\n",
    "                    ans = min(ans, abs(x2 - x1) * abs(y2 - y1))\n",
    "        return ans if ans != 1600000001 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        grid = {}\n",
    "        for i in range(n):\n",
    "            x, y = points[i]\n",
    "            grid[x * 40001 + y] = 1\n",
    "\n",
    "        \n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                p1, p2 = points[i], points[j]\n",
    "                x1, y1 = p1\n",
    "                x2, y2 = p2\n",
    "                if(x1 != x2 and y1 != y2):\n",
    "                    if x1*40001 + y2 in grid and x2*40001 + y1 in grid:\n",
    "                        res = min(res, abs(x1-x2) * abs(y1- y2))\n",
    "\n",
    "        return res if res != float('inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        hashset = set()\n",
    "        for i,j in points:\n",
    "            hashset.add((i,j))\n",
    "        res = inf \n",
    "        for i in range(len(points)-1):\n",
    "            for j in range(i,len(points)):\n",
    "                po1 = points[i]\n",
    "                po2 = points[j] \n",
    "                if po1[0] == po2[0] or po1[1] == po2[1]:\n",
    "                    continue \n",
    "                \n",
    "                # 2在1右上\n",
    "                if po1[0] < po2[0] and po1[1] < po2[1]:\n",
    "                    if (po1[0],po2[1]) in hashset and (po2[0],po1[1]) in hashset:\n",
    "                        res = min(res,abs(po2[0]-po1[0])*abs(po1[1]-po2[1]))\n",
    "                # 2在1左下\n",
    "                if po1[0] > po2[0] and po1[1] > po2[1]:\n",
    "                    if (po2[0],po1[1]) in hashset and (po1[0],po2[1]) in hashset:\n",
    "                        res = min(res,abs(po2[0]-po1[0])*abs(po1[1]-po2[1]))\n",
    "                # 2在1左上\n",
    "                if po1[0] > po2[0] and po1[1] < po2[1]:\n",
    "                    if (po2[0],po1[1]) in hashset and (po1[0],po2[1]) in hashset:\n",
    "                        res = min(res,abs(po2[0]-po1[0])*abs(po1[1]-po2[1]))\n",
    "                # 2在1右下\n",
    "                if po2[0] > po1[0] and po2[1] < po1[1]:\n",
    "                    if (po1[0],po2[1]) in hashset and (po2[0],po1[1]) in hashset:\n",
    "                        res = min(res,abs(po2[0]-po1[0])*abs(po1[1]-po2[1]))\n",
    "        if res > 10**9:\n",
    "            return 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        ps, n, ans = set(), len(points), 0\n",
    "        for x, y in points: ps.add((x, y))\n",
    "        for i in range(n):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i + 1, n):\n",
    "                x2, y2 = points[j]\n",
    "                if x1 != x2 and y1 != y2:\n",
    "                    if (x1, y2) in ps and (x2, y1) in ps:\n",
    "                        tmp = abs(x1 - x2) * abs(y1 - y2)\n",
    "                        if ans == 0 or ans > tmp: ans = tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        grid = {}\n",
    "        for i in range(n):\n",
    "            x, y = points[i]\n",
    "            grid[x * 40001 + y] = 1\n",
    "\n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                p1, p2 = points[i], points[j]\n",
    "                x1, y1 = p1\n",
    "                x2, y2 = p2\n",
    "                if (x1 != x2) and (y1 != y2):\n",
    "                    if x1 * 40001 + y2 in grid and x2 * 40001 + y1 in grid:\n",
    "                        res = min(res, abs(x1 - x2) * abs(y1 - y2))\n",
    "\n",
    "        return res if res != float(inf) else 0\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        # n = len(points)\n",
    "        # grid = {}\n",
    "        # for i in range(n):\n",
    "        #     x, y = points[i]\n",
    "        #     grid[x * 40001 + y] = 1\n",
    "\n",
    "        \n",
    "        # res = float('inf')\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i+1, n):\n",
    "        #         p1, p2 = points[i], points[j]\n",
    "        #         x1, y1 = p1\n",
    "        #         x2, y2 = p2\n",
    "        #         if(x1 != x2 and y1 != y2):\n",
    "        #             if x1*40001 + y2 in grid and x2*40001 + y1 in grid:\n",
    "        #                 res = min(res, abs(x1-x2) * abs(y1- y2))\n",
    "\n",
    "        # return res if res != float('inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        x_dict = {}  # x:[ylist]\n",
    "        y_dict = {}  # y:[xlist]\n",
    "        points = {tuple(p) for p in points}\n",
    "        for p in points:\n",
    "            x_dict.setdefault(p[0], set()).add(p[1])\n",
    "            y_dict.setdefault(p[1], set()).add(p[0])\n",
    "        res = 0\n",
    "        while points:\n",
    "            p = points.pop()\n",
    "            x = p[0]\n",
    "            y = p[1]\n",
    "            for y_ in x_dict[x]:\n",
    "                for x_ in y_dict[y]:\n",
    "                    if y_ != y and x_ != x and (x_, y_) in points:\n",
    "                        res = min(res, abs(x - x_) * abs(y - y_)) if res > 0 else abs(x - x_) * abs(y - y_)\n",
    "            x_dict[x].remove(y)\n",
    "            y_dict[y].remove(x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        rowmap = {}\n",
    "        rowlist = set()\n",
    "        for x, y in points:\n",
    "            if(x not in rowmap):\n",
    "                rowmap[x] = set()\n",
    "            rowmap[x].add(y)\n",
    "            rowlist.add(x)\n",
    "        rowlist = list(rowlist)\n",
    "        result = float('inf')\n",
    "        for i in range(len(rowlist)):\n",
    "            x1 = rowlist[i]\n",
    "            for j in range(i+1,len(rowlist)):\n",
    "                x2 = rowlist[j]\n",
    "                yset = rowmap[x1] & rowmap[x2]\n",
    "                if(len(yset) < 2):\n",
    "                    continue\n",
    "                yset = sorted(yset)\n",
    "                for i in range(1,len(yset)):\n",
    "                    result = min(result, (yset[i]-yset[i-1])*abs(x1-x2))\n",
    "        return result if result < float('inf') else 0\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "      x_to_y = defaultdict(set)\n",
    "      y_to_x = defaultdict(set)\n",
    "\n",
    "      for x, y in points:\n",
    "        x_to_y[x].add(y)\n",
    "        y_to_x[y].add(x)\n",
    "\n",
    "      xs = list(sorted(x_to_y.keys()))\n",
    "      ys = list(sorted(y_to_x.keys()))\n",
    "      \n",
    "      res = float(\"inf\")\n",
    "      for i in range(len(xs)):\n",
    "        for j in range(i + 1, len(xs)):\n",
    "          x1 = xs[i]\n",
    "          x1_ys = x_to_y[x1]\n",
    "          x2 = xs[j]\n",
    "          x2_ys = x_to_y[x2]\n",
    "          for m in range(len(ys)):\n",
    "            for n in range(m + 1, len(ys)):\n",
    "              y1 = ys[m]\n",
    "              y2 = ys[n]\n",
    "              y1_xs = y_to_x[y1]\n",
    "              y2_xs = y_to_x[y2]\n",
    "              if x1 in y1_xs and x1 in y2_xs and x2 in y1_xs and x2 in y2_xs and y1 in x1_ys and y1 in x2_ys and y2 in x1_ys and y2 in x2_ys:\n",
    "                res = min(res, (x2 - x1) * (y2 - y1))\n",
    "\n",
    "      return res if res != float(\"inf\") else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 按列排序\n",
    "    def minAreaRect1(self, points: List[List[int]]) -> int:\n",
    "        columns = collections.defaultdict(list)\n",
    "        for x, y in points:\n",
    "            columns[x].append(y)\n",
    "\n",
    "        lastx = {}\n",
    "        ans = float('inf')\n",
    "\n",
    "        for x in sorted(columns):\n",
    "            column = columns[x]\n",
    "            column.sort()\n",
    "            for j, y2 in enumerate(column):\n",
    "                for i in range(j):\n",
    "                    y1 = column[i]\n",
    "                    if (y1, y2) in lastx:\n",
    "                        ans = min(ans, (x - lastx[y1,y2]) * (y2 - y1))\n",
    "\n",
    "                    lastx[y1, y2] = x\n",
    "\n",
    "        return ans if ans < float('inf') else 0\n",
    "\n",
    "\n",
    "\n",
    "    # 枚举对角线\n",
    "    def minAreaRect(self, points):\n",
    "        S = set(map(tuple, points))\n",
    "        ans = float('inf')\n",
    "        for j, p2 in enumerate(points):\n",
    "            for i in range(j):\n",
    "                p1 = points[i]\n",
    "                if (p1[0] != p2[0] and p1[1] != p2[1] and\n",
    "                        (p1[0], p2[1]) in S and (p2[0], p1[1]) in S):\n",
    "                    ans = min(ans, abs(p2[0] - p1[0]) * abs(p2[1] - p1[1]))\n",
    "\n",
    "        return ans if ans < float('inf') else 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        mem = set()\n",
    "        for x, y in points:\n",
    "            mem.add((x, y))\n",
    "\n",
    "        result = float('inf')\n",
    "        for x1, y1 in points:\n",
    "            for x2, y2 in points:\n",
    "                if x1 < x2 and y1 < y2:\n",
    "                    if (x1, y2) in mem and (x2, y1) in mem:\n",
    "                        result = min(result, abs((x2 - x1) * (y2 - y1)))\n",
    "        \n",
    "        return result if result != float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minAreaRect(self, points):\n",
    "        S = set(map(tuple, points))\n",
    "        ans = float('inf')\n",
    "        for j, p2 in enumerate(points):\n",
    "            for i in range(j):\n",
    "                p1 = points[i]\n",
    "                if (p1[0] != p2[0] and p1[1] != p2[1] and\n",
    "                        (p1[0], p2[1]) in S and (p2[0], p1[1]) in S):\n",
    "                    ans = min(ans, abs(p2[0] - p1[0]) * abs(p2[1] - p1[1]))\n",
    "        return ans if ans < float('inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        pointSet = set(map(tuple, points))\n",
    "        minArea = float('inf')\n",
    "        \n",
    "        for (x1, y1) in points:\n",
    "            for (x2, y2) in points:\n",
    "                if x1 < x2 and y1 < y2:\n",
    "                    if (x1, y2) in pointSet and (x2, y1) in pointSet:\n",
    "                        area = (x2 - x1) * (y2 - y1)\n",
    "                        minArea = min(minArea, area)\n",
    "\n",
    "        return minArea if minArea != float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        res=float('inf')\n",
    "        points_set = set(map(tuple, points))\n",
    "        for i in range(len(points)):\n",
    "            temp1 = points[i]\n",
    "            for j in range(i):\n",
    "                temp2 = points[j]\n",
    "                if temp1[0]!=temp2[0] and temp1[1]!=temp2[1]:\n",
    "                    if (temp1[0],temp2[1]) in points_set and (temp2[0],temp1[1]) in points_set:\n",
    "                        res = min(res, abs(temp1[0]-temp2[0])*abs(temp1[1]-temp2[1]))\n",
    "        if res == float('inf'):\n",
    "            return 0\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "#         s=[]\n",
    "#         S = set(map(tuple, points))  #元组可哈希，而列表不可哈希\n",
    "#         for i in range(len(points)):\n",
    "#             for j in range(i+1,len(points)):\n",
    "#                 if (points[i][0],points[j][1]) in S and (points[j][0],points[i][1])in S and points[i][0]!=points[j][0] and points[i][1]!=points[j][1]:\n",
    "#                     s.append(abs((points[i][0]-points[j][0])*(points[i][1]-points[j][1])))\n",
    "#         return min(s) if s else 0\n",
    "class Solution(object):\n",
    "    def minAreaRect(self, points):\n",
    "        S = set(map(tuple, points))\n",
    "        ans = float('inf')\n",
    "        for j, p2 in enumerate(points):\n",
    "            for i in range(j):\n",
    "                p1 = points[i]\n",
    "                if (p1[0] != p2[0] and p1[1] != p2[1] and\n",
    "                        (p1[0], p2[1]) in S and (p2[0], p1[1]) in S):\n",
    "                    ans = min(ans, abs(p2[0] - p1[0]) * abs(p2[1] - p1[1]))\n",
    "        return ans if ans < float('inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        res=float('inf')\n",
    "        points_set = set(map(tuple, points))\n",
    "        for i in range(len(points)):\n",
    "            temp1 = points[i]\n",
    "            for j in range(i):\n",
    "                temp2 = points[j]\n",
    "                if temp1[0]!=temp2[0] and temp1[1]!=temp2[1]:\n",
    "                    if (temp1[0],temp2[1]) in points_set and (temp2[0],temp1[1]) in points_set:\n",
    "                        res = min(res, abs(temp1[0]-temp2[0])*abs(temp1[1]-temp2[1]))\n",
    "        if res == float('inf'):\n",
    "            return 0\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        s = set(tuple(p) for p in points)\n",
    "        n, res = len(points), inf\n",
    "        for i in range(n):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i + 1, n):\n",
    "                x2, y2 = points[j]\n",
    "                if x1 != x2 and y1 != y2 and (x1, y2) in s and (x2, y1) in s:\n",
    "                    res = min(res, abs(x1 - x2) * abs(y1 - y2))\n",
    "        return res if res != inf else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\r\n",
    "        x_dic = {}\r\n",
    "        for val in points:\r\n",
    "            if val[0] in x_dic:\r\n",
    "                x_dic[val[0]].add(val[1])\r\n",
    "            else:\r\n",
    "                x_dic[val[0]] = set([val[1]])\r\n",
    "        res = float('inf')\r\n",
    "        for key1 in x_dic:\r\n",
    "            for key2 in x_dic:\r\n",
    "                if key1 != key2:\r\n",
    "                    x = abs(key1 - key2)\r\n",
    "                    lis = list(x_dic[key1] & x_dic[key2])\r\n",
    "                    if len(lis) > 1:\r\n",
    "                        lis.sort()\r\n",
    "                        y = float('inf')\r\n",
    "                        for i in range(1, len(lis)):\r\n",
    "                            y = min(y, lis[i] - lis[i - 1])\r\n",
    "                        res = min(res, x * y)\r\n",
    "        if res == float('inf'):\r\n",
    "            return(0)\r\n",
    "        return(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        a = {}\n",
    "        for p in points:\n",
    "            if p[0] in a:\n",
    "                a[p[0]].add(p[1])\n",
    "            else:\n",
    "                a[p[0]] = {p[1]}\n",
    "\n",
    "        k = list(a.keys())\n",
    "        n = len(k)\n",
    "        ans = 10**9\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                s = a[k[i]].intersection(a[k[j]])\n",
    "                m = len(s)\n",
    "                if m >= 2:\n",
    "                    t = list(s)\n",
    "                    for g in range(m-1):\n",
    "                        for h in range(g+1,m):\n",
    "                            res = (k[i] - k[j])*(t[g] - t[h])\n",
    "                            ans = min(ans , abs(res))\n",
    "        if ans == 10**9:\n",
    "            return 0 \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\r\n",
    "        x_dic = {}\r\n",
    "        for val in points:\r\n",
    "            if val[0] in x_dic:\r\n",
    "                x_dic[val[0]].add(val[1])\r\n",
    "            else:\r\n",
    "                x_dic[val[0]] = set([val[1]])\r\n",
    "        res = float('inf')\r\n",
    "        for key1 in x_dic:\r\n",
    "            for key2 in x_dic:\r\n",
    "                if key1 != key2:\r\n",
    "                    x = abs(key1 - key2)\r\n",
    "                    lis = list(x_dic[key1] & x_dic[key2])\r\n",
    "                    if len(lis) > 1:\r\n",
    "                        lis.sort()\r\n",
    "                        y = float('inf')\r\n",
    "                        for i in range(1, len(lis)):\r\n",
    "                            y = min(y, lis[i] - lis[i - 1])\r\n",
    "                        res = min(res, x * y)\r\n",
    "        if res == float('inf'):\r\n",
    "            return(0)\r\n",
    "        return(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\r\n",
    "        ans = float('inf')\r\n",
    "        n = len(points)\r\n",
    "        if n < 4:\r\n",
    "            return 0\r\n",
    "        points = list(set(map(tuple, points)))\r\n",
    "        for i in range(n):\r\n",
    "            if ans == 1:\r\n",
    "                break\r\n",
    "            for j in range(i+1, n):\r\n",
    "                x1, y1 = points[i]\r\n",
    "                x2, y2 = points[j]\r\n",
    "                cur = abs(x1-x2) * abs(y1-y2)\r\n",
    "                if cur >= ans:\r\n",
    "                    continue\r\n",
    "                if x1 != x2 and y1 != y2 and (x1, y2) in points and (x2, y1) in points:\r\n",
    "                    ans = min(ans, cur)\r\n",
    "        return ans if ans != float('inf') else 0\r\n",
    "    \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\r\n",
    "        x_dic = {}\r\n",
    "        for val in points:\r\n",
    "            if val[0] in x_dic:\r\n",
    "                x_dic[val[0]].add(val[1])\r\n",
    "            else:\r\n",
    "                x_dic[val[0]] = set([val[1]])\r\n",
    "        res = float('inf')\r\n",
    "        for key1 in x_dic:\r\n",
    "            for key2 in x_dic:\r\n",
    "                if key1 != key2:\r\n",
    "                    x = abs(key1 - key2)\r\n",
    "                    lis = list(x_dic[key1] & x_dic[key2])\r\n",
    "                    if len(lis) > 1:\r\n",
    "                        lis.sort()\r\n",
    "                        y = float('inf')\r\n",
    "                        for i in range(1, len(lis)):\r\n",
    "                            y = min(y, lis[i] - lis[i - 1])\r\n",
    "                        res = min(res, x * y)\r\n",
    "        if res == float('inf'):\r\n",
    "            return(0)\r\n",
    "        return(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        s=[]\n",
    "        S = set(map(tuple, points))  #元组可哈希，而列表不可哈希\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i+1,len(points)):\n",
    "                if (points[i][0],points[j][1]) in S and (points[j][0],points[i][1])in S and points[i][0]!=points[j][0] and points[i][1]!=points[j][1]:\n",
    "                    s.append(abs((points[i][0]-points[j][0])*(points[i][1]-points[j][1])))\n",
    "        return min(s) if s else 0\n",
    "# class Solution(object):\n",
    "#     def minAreaRect(self, points):\n",
    "#         S = set(map(tuple, points))\n",
    "#         ans = float('inf')\n",
    "#         for j, p2 in enumerate(points):\n",
    "#             for i in range(j):\n",
    "#                 p1 = points[i]\n",
    "#                 if (p1[0] != p2[0] and p1[1] != p2[1] and\n",
    "#                         (p1[0], p2[1]) in S and (p2[0], p1[1]) in S):\n",
    "#                     ans = min(ans, abs(p2[0] - p1[0]) * abs(p2[1] - p1[1]))\n",
    "#         return ans if ans < float('inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        s=[]\n",
    "        S = set(map(tuple, points))\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i+1,len(points)):\n",
    "                if (points[i][0],points[j][1]) in S and (points[j][0],points[i][1])in S and points[i][0]!=points[j][0] and points[i][1]!=points[j][1]:\n",
    "                    s.append(abs((points[i][0]-points[j][0])*(points[i][1]-points[j][1])))\n",
    "        return min(s) if s else 0\n",
    "# class Solution(object):\n",
    "#     def minAreaRect(self, points):\n",
    "#         S = set(map(tuple, points))\n",
    "#         ans = float('inf')\n",
    "#         for j, p2 in enumerate(points):\n",
    "#             for i in range(j):\n",
    "#                 p1 = points[i]\n",
    "#                 if (p1[0] != p2[0] and p1[1] != p2[1] and\n",
    "#                         (p1[0], p2[1]) in S and (p2[0], p1[1]) in S):\n",
    "#                     ans = min(ans, abs(p2[0] - p1[0]) * abs(p2[1] - p1[1]))\n",
    "#         return ans if ans < float('inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        y_by_x = {}\n",
    "        for point in points:\n",
    "            if point[0] not in y_by_x:\n",
    "                y_by_x[point[0]] = set([point[1]])\n",
    "                continue\n",
    "            y_by_x[point[0]].add(point[1])\n",
    "\n",
    "        col_indices = list(y_by_x.keys())\n",
    "        col_indices.sort()\n",
    "\n",
    "        recs = []\n",
    "        for idx, x_1 in enumerate(col_indices[:-1]):\n",
    "            for x_2 in col_indices[idx + 1:]:\n",
    "                intersection = y_by_x[x_1].intersection(y_by_x[x_2])\n",
    "                if len(intersection) > 1:\n",
    "                    recs.append([x_2 - x_1, list(intersection)])\n",
    "\n",
    "        if not recs:\n",
    "            return 0\n",
    "\n",
    "        min_area = inf\n",
    "        for delta_x, ys in recs:\n",
    "            for idx, y1 in enumerate(ys[:-1]):\n",
    "                for y2 in ys[idx + 1:]:\n",
    "                    min_area = min(min_area, delta_x * abs(y2 - y1))\n",
    "        return min_area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        y_by_x = {}\n",
    "        for point in points:\n",
    "            if point[0] not in y_by_x:\n",
    "                y_by_x[point[0]] = set([point[1]])\n",
    "                continue\n",
    "            y_by_x[point[0]].add(point[1])\n",
    "\n",
    "        col_indices = list(y_by_x.keys())\n",
    "        col_indices.sort()\n",
    "\n",
    "        recs = []\n",
    "        for idx, x_1 in enumerate(col_indices[:-1]):\n",
    "            for x_2 in col_indices[idx + 1:]:\n",
    "                intersection = y_by_x[x_1].intersection(y_by_x[x_2])\n",
    "                if len(intersection) > 1:\n",
    "                    recs.append([x_2 - x_1, list(intersection)])\n",
    "        col_indices = None\n",
    "        y_by_x = None\n",
    "\n",
    "        if not recs:\n",
    "            return 0\n",
    "\n",
    "        min_area = inf\n",
    "        for delta_x, ys in recs:\n",
    "            for idx, y1 in enumerate(ys[:-1]):\n",
    "                for y2 in ys[idx + 1:]:\n",
    "                    min_area = min(min_area, delta_x * abs(y2 - y1))\n",
    "        return min_area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        y_by_x = {}\n",
    "        for point in points:\n",
    "            if point[0] not in y_by_x:\n",
    "                y_by_x[point[0]] = set([point[1]])\n",
    "                continue\n",
    "            y_by_x[point[0]].add(point[1])\n",
    "\n",
    "        col_indices = list(y_by_x.keys())\n",
    "        col_indices.sort()\n",
    "\n",
    "        recs = []\n",
    "        for idx, x_1 in enumerate(col_indices[:-1]):\n",
    "            for x_2 in col_indices[idx + 1:]:\n",
    "                intersection = y_by_x[x_1].intersection(y_by_x[x_2])\n",
    "                if len(intersection) > 1:\n",
    "                    recs.append([x_2 - x_1, list(intersection)])\n",
    "\n",
    "        if not recs:\n",
    "            return 0\n",
    "\n",
    "        min_area = inf\n",
    "        for delta_x, ys in recs:\n",
    "            for idx, y1 in enumerate(ys[:-1]):\n",
    "                for y2 in ys[idx + 1:]:\n",
    "                    print()\n",
    "                    min_area = min(min_area, delta_x * abs(y2 - y1))\n",
    "        return min_area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        H = {}\n",
    "        for x, y in points:\n",
    "            if y not in H:\n",
    "                H[y] = []\n",
    "            H[y].append(x)\n",
    "        Hp = {}\n",
    "        for y in H:\n",
    "            Hp[y] = set()\n",
    "            H[y].sort()\n",
    "            for i in range(len(H[y])):\n",
    "                for j in range(i + 1, len(H[y])):\n",
    "                    Hp[y].add((H[y][i], H[y][j]))\n",
    "        Y = list(Hp.keys())\n",
    "        res = float('inf')\n",
    "        for i, y1 in enumerate(Y):\n",
    "            for j in range(i + 1, len(Y)):\n",
    "                y2 = Y[j]\n",
    "                S = Hp[y1] & Hp[y2]\n",
    "                for x1, x2 in S:\n",
    "                    res = min(res, abs(y1 - y2) * abs(x1 - x2))\n",
    "        if res == float('inf'):\n",
    "            return 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 按列排序，将点键为x,值为y列表加入哈希表，将哈希表按x轴排序，遍历哈希表\n",
    "# 将每一列按y排序，枚举同一列的所有点，对于y1,y2找出它作为右边的最小矩形\n",
    "# 使用一个集合记录之前最晚遇到的y1,y2可以求出面积，更新答案，更新最晚\n",
    "# 出现的x值，遍历完成返回答案\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        ans = inf\n",
    "        cols = collections.defaultdict(list)  # 键为x轴，值为y轴列表\n",
    "        for x, y in points:\n",
    "            cols[x].append(y) \n",
    "        lastx = {}  # 保存y轴为(y1,y2)的线段最后出现的x轴\n",
    "        \n",
    "        for x in sorted(cols):  # 将哈希表按x轴排序\n",
    "            col = cols[x]\n",
    "            col.sort()  # 按y轴排序\n",
    "            for j, y2 in enumerate(col):  # 枚举所有下标和y值\n",
    "                for i in range(j):  # 枚举任意两个的y值的组合\n",
    "                    y1 = col[i]\n",
    "                    if (y1, y2) in lastx:  # 若之前有这条线，更新答案\n",
    "                        ans = min(ans, (x - lastx[y1, y2]) * (y2 - y1))\n",
    "                    lastx[y1, y2] = x  # 更新最后的x值\n",
    "        \n",
    "        return ans if ans != inf else 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minAreaRect(self, points):\n",
    "        columns = collections.defaultdict(list)\n",
    "        for x, y in points:\n",
    "            columns[x].append(y)\n",
    "        lastx = {}\n",
    "        ans = float('inf')\n",
    "\n",
    "        for x in sorted(columns):\n",
    "            column = columns[x]\n",
    "            column.sort()\n",
    "            for j, y2 in enumerate(column):\n",
    "                for i in range(j):\n",
    "                    y1 = column[i]\n",
    "                    if (y1, y2) in lastx:\n",
    "                        ans = min(ans, (x - lastx[y1,y2]) * (y2 - y1))\n",
    "                    lastx[y1, y2] = x\n",
    "        return ans if ans < float('inf') else 0\n",
    "\n",
    "# 作者：LeetCode\n",
    "# 链接：https://leetcode.cn/problems/minimum-area-rectangle/\n",
    "# 来源：力扣（LeetCode）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        minArea = sys.maxsize\n",
    "        mapx = {}\n",
    "        for i, point in enumerate(points):\n",
    "            if point[0] in mapx:\n",
    "                mapx[point[0]].append(point[1])\n",
    "            else:\n",
    "                mapx[point[0]] = [point[1]]\n",
    "        ans = float('inf')\n",
    "        lastx = {}\n",
    "        # 得到一个key的排序\n",
    "        for x in sorted(mapx):\n",
    "            ys = mapx[x]\n",
    "            ys.sort()\n",
    "            # 遍历所有y的组合\n",
    "            for j, y2 in enumerate(ys):\n",
    "                for i in range(j+1, len(ys)):\n",
    "                    y1 = ys[i]\n",
    "                    if (y1, y2) in lastx:\n",
    "                        ans = min(ans, (x-lastx[y1, y2])*abs(y2-y1))\n",
    "                    # 上一次的结果\n",
    "                    lastx[y1,y2] = x\n",
    "        return ans if ans < float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        columns = defaultdict(list)\n",
    "        for x, y in points:\n",
    "            columns[x].append(y)\n",
    "\n",
    "        lastX = {}\n",
    "        ans = float('inf')\n",
    "        for x in sorted(columns):\n",
    "            column = columns[x]\n",
    "            column.sort()\n",
    "            for j, y2 in enumerate(column):\n",
    "                for i in range(j):\n",
    "                    y1 = column[i]\n",
    "                    if (y1, y2) in lastX:\n",
    "                        ans = min(ans, (x - lastX[y1 , y2]) * (y2 - y1))\n",
    "                    lastX[y1, y2] = x\n",
    "        return int(ans) if ans < float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        columns = collections.defaultdict(list)\n",
    "        for x, y in points:\n",
    "            columns[x].append(y)\n",
    "        \n",
    "        seen = dict()\n",
    "        ans = float('inf')\n",
    "        for x in sorted(columns):\n",
    "            column = columns[x]\n",
    "            column.sort()\n",
    "            for j, y2 in enumerate(column):\n",
    "                for i in range(j):\n",
    "                    y1 = column[i]\n",
    "                    if (y1, y2) in seen:\n",
    "                        ans = min(ans, (y2 - y1) * (x - seen[(y1, y2)]))\n",
    "                    seen[(y1, y2)] = x\n",
    "\n",
    "        return ans if ans < float('inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        #按照x轴（即列）排序， 那么对于同一列的两个点(x,y1)和(x,y2)\n",
    "        #这可以通过记录下我们之前遇到的所有 (y1, y2) 点对来做到。\n",
    "        #使用一个 last_x_points 来存放在(y1, y2)点上最后一个x坐标。\n",
    "        #(因为我们需要计算最小面积，长和宽当然越小越好，所以只记录最后一个)\n",
    "        columns = defaultdict(list)\n",
    "        for x, y in points:\n",
    "            columns[x].append(y)\n",
    "        last_x_points = {}\n",
    "        ans = float('inf')\n",
    "        for x in sorted(columns):\n",
    "            column = columns[x]\n",
    "            column.sort()\n",
    "            for j, y2 in enumerate(column):\n",
    "                #只从[0, j]中找，保证y1和y2不会重复\n",
    "                for i in range(j):\n",
    "                    y1 = column[i]\n",
    "                    if (y1, y2) in last_x_points:\n",
    "                        ans = min(ans, (x - last_x_points[y1, y2]) * (y2 - y1))\n",
    "                    last_x_points[y1, y2] = x\n",
    "        return ans if ans < float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        minArea = sys.maxsize\n",
    "        mapx = {}\n",
    "        for i, point in enumerate(points):\n",
    "            if point[0] in mapx:\n",
    "                mapx[point[0]].append(point[1])\n",
    "            else:\n",
    "                mapx[point[0]] = [point[1]]\n",
    "        ans = float('inf')\n",
    "        lastx = {}\n",
    "        # 得到一个key的排序\n",
    "        for x in sorted(mapx):\n",
    "            ys = mapx[x]\n",
    "            ys.sort()\n",
    "            # 遍历所有y的组合\n",
    "            for j, y1 in enumerate(ys):\n",
    "                for i in range(j+1, len(ys)):\n",
    "                    y2 = ys[i]\n",
    "                    if (y1, y2) in lastx:\n",
    "                        print(y2, y1)\n",
    "                        ans = min(ans, (x-lastx[y1, y2])*(y2-y1))\n",
    "                    # 上一次的结果\n",
    "                    lastx[y1,y2] = x\n",
    "        return ans if ans < float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "\n",
    "        columns = collections.defaultdict(list)\n",
    "        for x, y in points:\n",
    "            columns[x].append(y)\n",
    "        lastx = {}\n",
    "        res = float('inf')\n",
    "\n",
    "        for x in sorted(columns):\n",
    "            column = columns[x]\n",
    "            column.sort()\n",
    "\n",
    "            for j, y2 in enumerate(column):\n",
    "                for i in range(j):\n",
    "                    y1 = column[i]\n",
    "\n",
    "                    if (y1, y2) in lastx:\n",
    "                        res = min(res, (x - lastx[y1, y2]) * ( y2 - y1 ))\n",
    "                    lastx[y1, y2] = x\n",
    "\n",
    "        return res if res < float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        cols = defaultdict(list)\n",
    "        for x,y in points:\n",
    "            cols[x].append(y)\n",
    "        last = {}\n",
    "        ans = float('inf')\n",
    "        for x in sorted(cols):\n",
    "            col = cols[x]\n",
    "            col.sort()\n",
    "            for j,y2 in enumerate(col):\n",
    "                for i in range(j):\n",
    "                    y1 = col[i]\n",
    "                    if (y1,y2) in last:\n",
    "                        ans = min(ans,(x-last[(y1,y2)])*(y2-y1))\n",
    "                    last[(y1,y2)] = x\n",
    "        return ans if ans < float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "class Solution:\n",
    "    def minAreaRect(self, points: List[List[int]]) -> int:\n",
    "        minArea = sys.maxsize\n",
    "        mapx = {}\n",
    "        for i, point in enumerate(points):\n",
    "            if point[0] in mapx:\n",
    "                mapx[point[0]].append(point[1])\n",
    "            else:\n",
    "                mapx[point[0]] = [point[1]]\n",
    "        ans = float('inf')\n",
    "        lastx = {}\n",
    "        # 得到一个key的排序\n",
    "        for x in sorted(mapx):\n",
    "            ys = mapx[x]\n",
    "            ys.sort()\n",
    "            for j, y2 in enumerate(ys):\n",
    "                for i in range(j+1, len(ys)):\n",
    "                    y1 = ys[i]\n",
    "                    if (y1, y2) in lastx:\n",
    "                        ans = min(ans, (x-lastx[y1, y2])*abs(y2-y1))\n",
    "                    # 上一次的结果\n",
    "                    lastx[y1,y2] = x\n",
    "        return ans if ans < float('inf') else 0"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
